package com.study.sort;

/**
 * - *@ClassName QuickSort
 * - *@Author LiuHuaBing
 * - *@Date 2021/12/8 10:27
 * - *@Version 1.0
 */
public class QuickSort {

    public static void main(String[] args) {
        int arr[] = {9, 5, 4, 8, 6, 2, -5, 93, 4};
        arr = quickSort2(arr, 0, arr.length - 1);
        for (int i : arr) {
            System.out.println(i);
        }
    }

    private static int[] quickSort1(int[] arr, int L, int R) {
        if (L < R) {
            int[] p = partition1(arr, L, R);
            quickSort1(arr, L, p[0]);
            quickSort1(arr, p[1], R);
        }
        return arr;
    }

    private static int[] partition1(int[] arr, int index, int right) {
        int marginIndex = right;
        int margin = arr[right];
        int left = index - 1;
        int temp;
        while (index < right) {
            if (arr[index] <= margin) {
                temp = arr[left + 1];
                arr[left + 1] = arr[index];
                arr[index] = temp;
                left++;
            }
            index++;
        }
        temp = arr[left + 1];
        arr[left + 1] = arr[right];
        arr[right] = temp;
        return new int[]{left, left + 1};

    }

    private static int[] quickSort2(int[] arr, int L, int R) {

        if (L < R) {
            int[] p = partition2(arr, L, R);
            quickSort2(arr, L, p[0]);
            quickSort2(arr, p[1], R);
        }
        return arr;

    }

    private static int[] partition2(int[] arr, int L, int R) {
        int margin = arr[R];
        int index = L;
        int left = L - 1;
        int right = R + 1;
        int temp;
        while (index < right) {
            if (arr[index] < margin) {
                temp = arr[index];
                arr[index] = arr[left + 1];
                arr[left + 1] = temp;
                left++;
                index++;
            } else if (arr[index] > margin) {
                temp = arr[index];
                arr[index] = arr[right - 1];
                arr[right - 1] = temp;
                right--;
            } else {
                index++;
            }
        }
        return new int[]{left, right};
    }
}
